/**********************************************************

@description:binary balance tree,bst belong to the first char of three developer
@method1:step1:create a bst tree step2: balance it
*File Name:avl.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Sun 27 Apr 2025 01:38:52 AM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max(a,b) ((a)>(b)?(a):(b))
typedef struct tnode{
	int data;
	unsigned int height;
	struct tnode* lchild;
	struct tnode* rchild;
}tnode;

unsigned int getHeight(tnode *t){
	return t ? t->height :0 ;
}
void resetHeight(tnode *t){
	if(!t){
		return;
	}
	if(!(t->lchild) && !(t->rchild)){
		t->height=1;
	}else{
		resetHeight(t->lchild);
		resetHeight(t->rchild);
		t->height=max(getHeight(t->lchild),getHeight(t->rchild))+1;
		return;
	}
}

typedef void (*rotation)(tnode**);
void rr(tnode **root){
	if(!(*root))
		return;
	tnode *rchild=(*root)->rchild;
	if(!rchild)
		return;
	(*root)->rchild=rchild->lchild;
	rchild->lchild=(*root);
	*root=rchild;
}
void rl(tnode **root){
	if(!(*root))
		return;
	tnode *rchild=(*root)->rchild;
	if(!rchild)
		return;
	tnode *rlchild=rchild->lchild;
	if(!rlchild)
		return;
	tnode *tmpl=rlchild->lchild;
	tnode *tmpr=rlchild->rchild;
	rlchild->lchild=(*root);
	rlchild->rchild=rchild;
	(*root)->rchild=tmpl;
	rchild->lchild=tmpr;
	*root=rlchild;
}
void ll(tnode **root){
	if(!(*root))
		return;
	tnode *lchild=(*root)->lchild;
	if(!lchild)
		return;
	(*root)->lchild=lchild->rchild;
	lchild->rchild=(*root);
	*root=lchild;
}
void lr(tnode **root){
	if(!(*root))
		return;
	tnode *lchild=(*root)->lchild;
	if(!lchild)
		return;
	tnode *lrchild=lchild->rchild;
	if(!lrchild)
		return;
	tnode *tmpl=lrchild->lchild;
	tnode *tmpr=lrchild->rchild;
	lrchild->lchild=lchild;
	lrchild->rchild=(*root);
	(*root)->lchild=tmpr;
	lchild->rchild=tmpl;
	*root=lrchild;
}
tnode* init_tnode(int data){
	tnode* n=(tnode*)malloc(sizeof(tnode));
	if(!n){
		printf("init_tnode malloc error!");
		return NULL;
	}
	n->data=data;
	n->height=0;
	n->lchild=NULL;
	n->lchild=NULL;
	return n;
}
tnode* bstSearch(tnode* t,int data){
	if(!t)
		return NULL;
	if(t->data==data){
		return t;
	}else if(data<t->data){
		bstSearch(t->lchild,data);
	}else{
		bstSearch(t->rchild,data);
	}
}
void bstInsert(tnode **t,int data){
	if(!(*t)){
		tnode* n=init_tnode(data);
		*t=n;
	}else if(data<(*t)->data){
		bstInsert(&(*t)->lchild,data);
	}else if(data>(*t)->data){
		bstInsert(&(*t)->rchild,data);
	}
}

int ajust(tnode **t){
	if(!(*t)){
		return -1;
	}
	int lheight;
	int rheight;
	int flag;
	int ret=1;
ajust:
	resetHeight(*t);
	lheight=getHeight((*t)->lchild);
	rheight=getHeight((*t)->rchild);
	if(abs(lheight-rheight)<=1)
		return 0;
	else if(lheight-rheight==2)
		goto ljust;
	else if(rheight-lheight==2)
		goto rjust;
	else if(rheight-lheight>2){
		ret=ajust(&(*t)->rchild);
		if(!ret)
			 goto rjust;
	}else if(lheight-rheight>2){
		ret=ajust(&(*t)->lchild);
		if(!ret)
			goto ljust;
	}
ljust:
	if((*t)->lchild->rchild){
		lr(t);
	}else{
		ll(t);
	}
	goto ajust;
rjust:
	if((*t)->rchild->lchild){
		rl(t);
	}else{
		rr(t);
	}
	goto ajust;
}

typedef void (*visit)(tnode*);
void pn(tnode* n){
	if(n)
		printf("%d ",n->data);
}
void preorder(tnode* t,visit v){
	v(t);
	if(t){
		preorder(t->lchild,v);
		preorder(t->rchild,v);
	}
}
void inorder(tnode* t,visit v){
	if(t){
		inorder(t->lchild,v);
		v(t);
		inorder(t->rchild,v);
	}
}
void postorder(tnode* t,visit v){
	if(t){
		postorder(t->lchild,v);
		postorder(t->rchild,v);
		v(t);
	}
}
int main(int argc,char **argv){
	tnode* t;
//	int nums[13]={8,6,10,9,11,23,14,1,13,2,9,7,5};
//	int nums[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};
	int nums[13]={13,12,11,10,9,8,7,6,5,4,3,2,1};
	//int nums[3]={1,2,3};
	for(int i=0;i<13;i++){
		bstInsert(&t,nums[i]);
	}
	resetHeight(t);
	ajust(&t);
	printf("original arr:");
	for(int i=0;i<13;i++){
		printf("%d ",nums[i]);
	}
	printf("\npreorder:");
	preorder(t,pn);
	printf("\ninorder:");
	inorder(t,pn);
	printf("\npostorder:");
	postorder(t,pn);
	printf("\n");
	return 0;
}
